package ch13;

public class MergeSorter 
{
	private int[] a;
	
	public MergeSorter(int[] anArray)
	{
		a = anArray;
	}
	
	public void sort()
	{
		if(a.length <= 1){
			return;
		}
		
		int[] first = new int[a.length / 2];
		int[] second = new int[a.length / 2];
		
		for(int i = 0; i < first.length; i ++)
		{
			first[i] = a[i];
		}
		
		for(int j = 0; j < second.length; j ++)
		{
			second[j] = a[first.length + j];
		}
		
		MergeSorter firstSorter = new MergeSorter(first);
		firstSorter.sort();
		
		MergeSorter secondSorter = new MergeSorter(second);
		secondSorter.sort();
		
		merge(first, second);
	}
	
	private void merge(int[] first, int[] second)
	{
		int iFirst = 0;
		int iSecond = 0;
		int j = 0;
		
		while(iFirst < first.length && iSecond < second.length)
		{
			if(first[iFirst] < second[iSecond]) {
				a[j] = first[iFirst];
				iFirst ++;
			} else {
				a[j] = second[iSecond];
				iSecond ++;
			}
			j ++;
		}
		
		while (iFirst < first.length) 
		{
			a[j] = first[iFirst];
			iFirst ++;
			j ++;
		}
		
		while (iSecond < second.length)
		{
			a[j] = second[iSecond];
			iSecond ++;
			j ++;
		}
	}

}
